The present invention is directed to a method and apparatus for compressing digital image data such that data transmission speed matches the speed of an associated modem. More specifically, the invention accomplishes image transmission by implementing multiple compressors, each of which compresses image data to achieve a different output image quality level. Throughout transmission, the invention continues to send the image data to the compressor that will process it such that an appropriate level of image quality will be retained, while simultaneously outputting it at a speed that will result in efficient serial data transmission.
The transmission of electronic data via facsimile machines and similar devices has become quite common, and efforts to transmit significantly larger volumes of this data within equal and even substantially shortened periods of time are constantly being made. This is true not only to allow data to be sent from one location to another at faster speeds and thereby cause less inconvenience to the user, but to enable more complex data to be transmitted between the same locations without drastically increasing the required transmission time. For example the facsimile transmission time for a detailed halftoned image will be many times more than that of a simple sheet of black text on a white page when using the same fax machine. By the same token, fax transmission of a color image will require an even greater amount of time than its greatly detailed halftoned counterpart.
The xe2x80x9csendingxe2x80x9d portion of fax transmission includes scanning the original image and generating a corresponding digital image thereof, followed by serial transmission of digital image data to a receiving fax machine. Without any form of data reduction, transmission of color image data files via facsimile would require extensive resourcesxe2x80x94very fast modems and/or large buffersxe2x80x94and would still take a great deal of time, thereby causing such transmission to become very expensive and therefore, impractical. Thus, some form of data compression is typically employed prior to fax transmission of color image data.
The JPEG (Joint Photographic Experts Group) standard provides a well known method of compressing electronic data. JPEG uses the discrete cosine transform (DCT) to map spatial data into spatial frequency domain data. Briefly, first JPEG requires transforming an 8xc3x978 block of pixels into a set of 8xc3x978 coefficients using the DCT to produce a DC coefficient (DCC), and a set of AC coefficients (ACCs). The DCC and ACCs are quantized, rounded to the nearest whole number and arranged in a one dimensional vector which is encoded into a bit stream.
Because color image data is so complex, ordinary data compression schemes require high compression ratios to be applied in order to complete the transmission within an acceptable time frame. Higher compression ratios lead to more data loss, typically at the higher end of the frequency range.
Successful fax transmission requires a proper correspondence between the compression ratio being applied to the image and the CPU speed of the sending fax machine. In other words, if the compression ratio is smaller than necessary for a given CPU speed, the CPU will have to be slowed down, or the data will have to wait to be transmitted and an appropriately sized buffer will be required. On the other hand, high compression levels mean that very few bits will be generated and less data will have to be sent through the modem. If the compression ratio is high relative to the CPU speed the modem will become idle waiting for the CPU to complete image processing and transmit more data. Since modems are typically configured to detect a large lapse in data transmission as the end of transmission, this large idle time typically causes the modem to disconnect. Thus, it is advantageous to continue the stream of data from the sending fax machine to the receiving fax machine, and eliminate gaps in the data stream. One way to do this is obviously to implement a faster JPEG compressor which can keep the data moving through the modem even if a high compression ratio is used. However, this solution results in significant cost increases and may be impractical.
One way to maintain proper compression ratio to clock speed correspondence is to provide multiple compressors to which portions of the digital image data may be transmitted. If the portion of the image being processed contains a lot of pictorial or other data that requires high quality reproduction, that data should be processed by the compressor which will provide the best image quality. However, if the portion of the image being processed contains text or other data that does not require high quality reproduction, that image data can be routed to a compressor that will produce a lower quality output to benefit from the fact lower quality output can be produced by the compressor at a much faster processing speed. In fact when text or other simple data is being processed, differences between image quality that is produced by a high quality output producing processor and that produced by a lower quality output producing processor will hardly be noticed by the human eye.
All pixels, and therefore blocks of pixels, are defined using a certain number of bits. In an image processing operation known as vector quantization (VQ), a block of Xxc3x97Y pixels is mapped to a single xe2x80x9ccodewordxe2x80x9d which is defined using a smaller number of bits than the number required by the original block. Codewords are stored in transmitting, receiving and storage devices, and each codeword is associated with a pre-defined set of image data. The codeword to which each pixel block is mapped is that which is associated with image data that most closely matches the image data in the pixel block. The typical process includes mapping the pixel block to a codeword, storing the codeword or transmitting it to a receiving device, and then mapping the codeword back to image data when it is retrieved from storage or received at the receiving device. Since codebook storage and codeword transmission require less space and time than storage and transmission of original image data, this process greatly reduces the resources required to reproduce the original image data.
There are typically many more combinations of pixel blocks than there are available codewords, and as indicated by the term xe2x80x9cquantizationxe2x80x9d several input blocks can be mapped to a single codeword. For a fixed number of codewords, increasing the size of the pixel block reduces the quality of mapping and reconstruction since more actual image data must be mapped to the same number of codewords. Some drawbacks of VQ are that codebook design is often very complex, and that large amounts of time are usually required to search through the codebook and to match blocks to the appropriate codeword. While codebook design can be performed off-line, block matching searches must be performed on-line.
In hierarchical vector quantization (HVQ), block matching searches are performed two samples at a time. Thus, look up tables (LUTs) can be used directly to perform HVQ in two or more stages. In the first stage, two image pixels are mapped to one codeword, reducing the number of samples by a factor of 2. In the next stage, the process is repeated to map pairs of codewords to single codewords. Preferably, codewords are grouped in a direction perpendicular to the one used for the previous level. As the process continues, the resulting codewords are mapped to larger and larger amounts of data.
HVQ allows for a rough approximation of the content of each image block using simple look-up table operations. The final codeword represents a block approximation and can, therefore be directly mapped to other quantities which describe certain characteristics of the approximated block, such as block activity. HVQ codebook design methods follow standard VQ codebook design algorithms and is usually performed by designing the codebooks for a single stage at a time.
The following disclosures may be relevant to aspects of the present invention:
U.S. Pat. No. 5,699,457 to Adar et al. issued Dec. 16, 1997 discloses a method of bit rate control and block allocation for discrete cosine transform (DCT) image signal compression includes the steps of (a) partitioning the image signals in blocks representing portions of the total image, (b) calculating DCT coefficients for image data in all blocks, (c) obtaining a measure of block activity (BACT) for each block based on DCT coefficients and for the total image activity (ACT) as a sum of the measures of all block activity, and (d) determining a code allocation factor (AF) for each block based on the ratio of block activity (BACT) to target code volume (TCV data) for the coded image data. The method also includes (e) allocating bits for each block using the allocation factor (AF) for each block and the target code volume (DCV data).
U.S. Pat. No. 5,699,170 to Yokose et al. issued Dec. 16, 1997 discloses an image communication system wherein transmission of an image between an image transmission apparatus and an image reception apparatus which include image output sections having different performances can be performed without making an inquiry for the performance prior to transmission. An image is inputted by an image input section and sent to a hierarchization section in the image transmission apparatus. The hierarchization section converts the inputted image into hierarchic communication data and transmits hierarchized data to a selection section of the image reception apparatus. The selection section extracts only necessary data from the hierarchic communication data transmitted thereto in accordance with the performance of an image output section of the image reception section and then sends the necessary data to the image output section after, if necessary, they are converted into image data. The image output section visualize the image data transmitted thereto from the selection section.
U.S. Pat. No. 5,642,438 to Babkin issued Jun. 24, 1997 discloses image compression implementing a fast two-dimensional discrete cosine transform. More specifically, Babkin discloses a method and apparatus for the realization of two-dimensional discrete cosine transform (DCT) for an 8xc3x978 image fragment with three levels of approximation of DCT coefficients.
U.S. Pat. No. 5,341,441 to Maeda et al. issued Aug. 23, 1994 discloses method and apparatus for coding image information, and a method of creating code books. A coding apparatus divides digital image information into pixel blocks each having a size of Mxc3x97N pixels, and subjects the image information to vector quantization in block units. The pixel blocks are orthogonally transformed and the characteristics and sequency components of the pixel blocks are detected. Each pixel block is divided into a plurality of sub-blocks in conformity with the detected sequency components. Respective ones of the plurality of divided and outputted sub-blocks are scalar-quantized into sub-vectors of a predetermined number of bits in conformity with the characteristics of the pixel blocks. Respective ones of the scalar-quantized values of the quantized sub-blocks are vector-quantized in conformity with the characteristics of the pixel blocks, these vector-quantized reproduction vector codes are combined and the result is subjected to further vector quantization.
Pending U.S. Ser. No. 09/075,935 filed on May 12, 1998 by Ricardo L. de Queiroz and assigned to the assignee of the present invention discloses an encoding and/or decoding method and apparatus which incorporates decoding commands into a compressed file. The decoding commands are instructions carried along to a decompressor and implement processing performed in the compressed domain. Then, the decompressor processes the data while decompressing it. This reduces the computation time for imaging operations.
Pending U.S. Ser. No. 09/119,023 filed on Jul. 20, 1998 by Ricardo L. deQueiroz and assigned to the assignee of the present application discloses a method and apparatus for compressing digital image data to improve the efficiency of serial data transmission. The invention accomplishes image compression by performing the most complex portions of a standard compression technique on a smaller amount of data than the usual 8xc3x978 block of image data. The invention includes a fast JPEG compressor based on a modified two-dimensional discrete cosine transform.
Pending US Patent Applications identified by attorney docket numbers D/98011 and D/98011Q to deQueiroz et al. entitled xe2x80x9cMethod and Apparatus for Using Multiple Transforms to Fill a Buffer for Enhanced Image Data Transmissionxe2x80x9d and xe2x80x9cApparatus for Using Multiple Transforms to Fill a Buffer for Enhanced Image Data Transmissionxe2x80x9d both assigned to the assignee of the present invention disclose methods and apparatus"" for compressing digital image data to improve the efficiency of serial data transmission. More specifically, the invention uses a buffer to hold processed image data until the modem is ready to transmit it. The amount of image data residing in the buffer is continuously checked, and one of several image processing modules is selected to process the data based upon the volume of data that resides in the buffer.
All of the references cited herein are incorporated by reference for their teachings.
Accordingly, although known apparatus and processes are suitable for their intended purposes, a need remains for a method and apparatus that can efficiently process digital image data and improve the efficiency of serial data transmission.
In accordance with one aspect of the invention there is provided a method of improving the speed and efficiency of electronic data transmission, which includes the steps of acquiring input image data which represents the light intensity of an image; segmenting the input image data to form a plurality of image data blocks; selecting, based on an image content, a module for receipt of an input image data block; and processing the received image data block in the module.
In accordance with another aspect of the invention, module selection in a method of improving the speed and efficiency of electronic data transmission includes obtaining an image data block; mapping the image data block to a single codeword using at least one look up table; and transmitting the image data block to a module which has been designated by the single codeword.
In accordance with yet another aspect of the invention there is provided an apparatus for improving the speed and efficiency of electronic data compression, which includes a segmenter which divides image data into a plurality of input image data blocks, wherein the image data corresponds to the light intensity of an original image; a plurality of image processing modules communicating with the segmenter, wherein any of the modules may process the segmented image data blocks; and an image analyzer communicating with the input image data blocks and with the modules to designate one of the modules for processing of a segmented image data block, based upon a content of the segmented image data block.
In accordance with still another aspect of the invention the image analyzer of an apparatus for improving the speed and efficiency of electronic data transmission includesan input data mapping device which maps each image data block to one codeword using a look up table; and a director which transmits the image data block to a module which has been designated by the single codeword.
The present invention deals with a common problem in digital image processing systemsxe2x80x94obtaining an effective yet cost efficient way to supply a continuous stream of complex image data from a sending fax machine to a receiving fax machine. One way to solve this problem includes using multiple compressors each having different data compression rates, and selecting the appropriate compressor for processing blocks of the image data based upon the content contained therein. Specifically, if the activity in the block is lowxe2x80x94there are few variations between pixel values in a single block, the image data will be processed by a module that processes data at a relatively high speed, even though some image quality may be lost. If block activity is high the data will be processed by the module that will produce the best image quality, albeit at a slower speed. While some areas of the original document will be reproduced at a lesser accuracy level, the overall quality of the output fax will be sufficient for most purposes.